// Package tree /*
/*

方法1：递归
时间复杂度：O(n)
空间复杂度：O(n)

case1:

r:

*/
package tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	return check(root, root)
}

// 通过两个指针同步朝相反的方向移动，判断当前两个指针所指向的值是否相等
func check(p, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
}

// 通过队列判断，一开是先将根节点放入队列，循环条件是队列长度是否大于0，每次循环从队列
// 中取出两个元素（让后从队列中删除这两个元素），如果这两个元素均为nil说明当前节点相等，进入下一次循环，
// 如果有一个为nil则返回false，
// 如果两个元素值不相等则直接返回false，之后按顺序将first.Left, second.Right, first.Right, second.Left放入队列
func isSymmetric1(root *TreeNode) bool {
	q := make([]*TreeNode, 0)
	q = append(q, root, root)
	for len(q) > 0 {
		u, v := q[0], q[1]
		q = q[2:]
		if u == nil && v == nil {
			continue
		}
		if u == nil || v == nil {
			return false
		}
		if u.Val != v.Val {
			return false
		}
		q = append(q, u.Left, v.Right, u.Right, v.Left)
	}
	return true
}
